1、暴力 BFS 会超时:状态是「空格位置 + 目标棋子位置」,四维状态数量极大,500 组询问完全跑不动。
2、状态压缩优化:只保留空格在目标棋子上下左右 4 个相邻位置的有效状态,记为 (x,y,dir),(x,y) 是目标棋子坐标,dir 是空格相对它的方向(上下左右 0~3)。
3、预处理:固定目标棋子不动,用 BFS 预处理空格从目标棋子某一邻位绕到另一邻位的最少步数,预先建图连边。
4、单次询问:
先用 BFS 算出初始空格走到目标棋子某一侧的代价;
在预处理好的图上跑 SPFA 最短路,模拟目标棋子一步步向终点挪动;
若终点可达输出最短路,否则 - 1。